package code.D1221;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * author： yeswater
 * create： 2023/12/22
 *
 * 根据身高重建队列
 *
 * people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
 */
public class T406 {
    /**
     * 解题思路：先排序再插入
     * 1.排序规则：按照先H高度降序，K个数升序排序
     * 2.遍历排序后的数组，根据K插入到K的位置上
     *
     * 核心思想：高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求
     *
     */
    
    // https://leetcode.cn/problems/queue-reconstruction-by-height/solutions/23208/406-gen-ju-shen-gao-zhong-jian-dui-lie-java-xian-p/
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1,o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
    
        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            list.add(i[1], i);
        }
        return list.toArray(new int[list.size()][2]);
    }
}
